package Day2025_03_05;

import java.util.ArrayList;
import java.util.List;

class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() {
        return key;
    }
    public V getValue() {
        return value;
    }
}

public class LeetCode662 {
    public int widthOfBinaryTree(TreeNode root) {
        int maxLen = 0;
        if (root == null) return maxLen;
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<TreeNode, Integer>(root, 1));
        while (!q.isEmpty()) {
            Pair<TreeNode, Integer> cur1 = q.get(0);
            Pair<TreeNode, Integer> cur2 = q.get(q.size() - 1);
            maxLen = Math.max(cur2.getValue() - cur1.getValue() + 1, maxLen);
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for (Pair<TreeNode, Integer> ret : q) {
                TreeNode cur = ret.getKey();
                int index = ret.getValue();
                if (cur.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(cur.left, index * 2));
                }
                if (cur.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(cur.right, index * 2 + 1));
                }
            }
            q = tmp;
        }
        return maxLen;
    }
}
